There is known an inner product operation circuit as shown in FIG. 5 for calculating an inner product ad+be+cf of two vectors A(a,b,c) and B(d,e,f). "R" expresses a pipeline register for a high speed operation in FIG. 5. FIG. 5 is attained by combining a multiplier-adder as shown in FIG. 6.
The operation of the multiplier-adder (FIG. 6) is shown in FIG. 7. Namely the partial products X.sub.i * y.sub.j of the multiplicands (X.sub.3, X.sub.2, X.sub.1, X.sub.0) and the multiplier factors (Y.sub.2, Y.sub.1, Y.sub.0) are added to the addends (L.sub.7, L.sub.6, L.sub.5, L.sub.4, L.sub.3, L.sub.2, L.sub.1, L.sub.0). The operation results (P.sub.7, P.sub.6, P.sub.5, P.sub.4, P.sub.3, P.sub.2, P.sub.1, P.sub.0) are obtained thereby.
A carry-save system is utilized for the calculation shown in FIG. 7. The carry-save system is an add system which decreases the number of partial product gradually. In the carry-save system, three signals of the same digit position are added by a full adder. Two signals, a carry signal and a sum signal are generated thereby. When the partial products which should be added have been reduced to two signals, carry signal and a sum signal per digit position, the carry-add operation is performed. The operation result P is obtained thereby.
A carry-add takes the most time in the operation of FIG. 7. Therefore, generally, a redundancy binary notation is utilized for an input and an output, because it does not need the carry-add. The operation of the multiplier-adder using a redundancy binary notation is shown in FIG. 8.
The multiplier-adder shown in FIG. 8 does not execute the last carry-add, because the operation result has redundancy notation (J.sub.7, J.sub.6, J.sub.5, J.sub.4, J.sub.3, J.sub.2, J.sub.1, J.sub.0) and (K.sub.7, K.sub.6, K.sub.5, K.sub.4, K.sub.3, K.sub.2, K.sub.1, K.sub.0).
When an inner product operation circuit is constructed by combining multiplier-adders, the output from one multiplier-adder is connected to the addend input of the next multiplier-adder. The input addend of FIG. 8 also represented by the redundancy notation (A.sub.7, A.sub.6, A.sub.5, A.sub.4, A.sub.3, A.sub.2, A.sub.1, A.sub.0) and (B.sub.7, B.sub.6, B.sub.5, B.sub.4, B.sub.3, B.sub.2, B.sub.1, B.sub.0).
When data in a redundancy binary notation is represented by two bits, a sum and a carry for each r bits, "r" is a "redundancy index" of this data. The redundancy index r of the data of FIG. 8 is 1.
The multiplier-adder of FIG. 8 is shown in FIG. 9. The input addend and the operation result are represented by two arrows in FIG. 9. The input addend and the operation result are represented by two arrows as shown in FIG. 9 to indicate that the data is represented by two signals corresponding to a carry and a sum for each bit.
The inner product operation circuit using the multiplier-adder is shown in FIG. 10. A carry-adder for obtaining a operation result is only used on the last step in case of the inner product operation circuit of FIG. 10. Because each multiplier-adder does not perform a carry-add, the inner product operation circuit is operated at high speed. But the number of registers for transmitting data is twice as many as a circuit not using a redundancy notation such as FIG. 5.
A conventional program automatically generates the hardware description of the multiplier-adder shown in FIG. 8 when supplied with the respective word lengths of a multiplier factor, a multiplicand, an addend and an output. The principle is shown in FIG. 11. The constant 0 is inserted as digit fillers to conform the shape of the partial products. Then the signals which are allocated to the full adders (FA) are arranged regularly as shown in FIG. 12.
It is difficult to automatically generate the hardware description because the shape of the partial products as shown in FIG. 8 is irregular. As such, a constant 0 is inserted as shown in FIGS. 11 and 12, thus regularizing the shape of the partial product and facilitating automatic generation of the hardware description.
Because the shape made by the partial product and the input addend becomes a rectangle of eight times five (8*5), the program generating the hardware description automatically generates the full adders of eight times five (8*5). Then the corresponding signals are connected to each adder as shown in FIG. 12.
FIG. 12 includes several useless full adders wherein a constant 0 is added to another constant 0. In a co-pending Japanese patent application (Hei 4-167727) entitled "Method FOR COMPRESSING A LOGIC CIRCUIT", a redundant circuit eliminating program is disclosed. The program eliminates the useless full adders and serves to convert a given circuit to an equivalent and smaller circuit. Since the output of the full adder is a constant, the full adder is replaced with a constant supplying circuit.
The useless full adders are eliminated from the circuit by using the redundant circuit eliminating program. The circuit in FIG. 13 is obtained thereby. Because FIG. 13 is an irregular circuit, it is difficult to make the program directly generate such a hardware description automatically. However, the hardware description shown in FIG. 13 can be generated by using the simple program for automatically generating a regular hardware description and the program for eliminating the redundant circuit.
Each multiplier-adder in the above noted inner product operation circuit transmits data by the redundancy notation wherein the redundancy index is 1. As such, the number of pipeline registers is twice as many as in methods wherein redundancy notation is not used. In addition, each multiplier-adder is separated from a carry-adder in the above noted inner product operation circuit, thus providing faster operation and enabling completion of the operation before the end of the required cycle period. However, this hardware description results in a circuit having plural pipeline registers which unnecessarily increases size, complexity and cost. As such, there is a need for a hardware description having a reduced size.